# 107. 二叉树的层序遍历 II
# 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
#
# 示例 1：
# 输入：root = [3,9,20,null,null,15,7]
# 输出：[[15,7],[9,20],[3]]
#
# 示例 2：
# 输入：root = [1]
# 输出：[[1]]
#
# 示例 3：
# 输入：root = []
# 输出：[]

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def levelOrderBottom(self, root):
        from collections import deque
        que = deque()
        res = []
        if not root:
            return res
        que.append(root)
        while que:
            tmp = []
            size = len(que)
            for i in range(size):
                node = que.popleft()
                tmp.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            res.insert(0,tmp) # 这里也可以用append秘密，最后显示的时候再反转一下就行
        return res

if __name__ == '__main__':
    a32 = TreeNode(7)
    a31 = TreeNode(15)
    a21 = TreeNode(9)
    a22 = TreeNode(20,a31,a32)
    a11 = TreeNode(3,a21,a22)
    tmp = Solution()
    res = tmp.levelOrderBottom(a11)
    print(res)
